%\documentclass[preprint,12pt]{elsarticle}

%\usepackage{amsfonts,mathbbol} 
%\usepackage{amssymb}
%\usepackage{amsmath}
%\usepackage{amsthm}
%\usepackage{graphicx}
%\usepackage{subfigure}
%\usepackage{verbatim}

%\usepackage{epsfig}
%\usepackage{mathsymb}
%\usepackage{algorithmic}

%\newtheorem{definition}{{\bf Definition}}
%\newtheorem{theorem}{{\bf Theorem}}
%\newtheorem{lemma}{{\bf Lemma}}
%\newtheorem{corollary}{{\bf Corollary}}
%\newtheorem{observation}{{\bf Observation}}


\renewcommand{\comment}[1]{{\bf Our response: #1}}
%
%
%\newcommand{\commentv}[1]{{\bf **Victor: #1**}}
%\newcommand{\commente}[1]{{\bf **Enrico: #1**}}
%\newcommand{\commentz}[1]{{\bf **Zinovi: #1**}}
%%\newcommand{\commentv}[1]{}
%%\newcommand{\commente}[1]{}
%%\newcommand{\commentz}[1]{}
%
%%%%%NOTATION%%%%%%%%
%\newcommand{\type}{\ensuremath{\theta}}%type
%\newcommand{\types}{\ensuremath{\Theta}}%space of all types
%\newcommand{\s}{\ensuremath{s}}%strategy
%\renewcommand{\S}{\ensuremath{S}}
%\newcommand{\ut}{\ensuremath{u}}%terminal utility
%\newcommand{\uet}{\ensuremath{\widehat{u}}}%expected utility by type
%\newcommand{\ue}{\ensuremath{\widetilde{u}}}%expected utility 
%%\newcommand{\ud}{\ensuremath{\hat{u}}}%distributional utility
%\renewcommand{\d}{\ensuremath{h}}%distribution of actions
%\renewcommand{\a}{\ensuremath{a}}%action
%\newcommand{\A}{\ensuremath{A}}%action set
%\newcommand{\as}{\ensuremath{{\bf a}}}%action profile
%\renewcommand{\b}{\a}%bid
%\renewcommand{\i}{\ensuremath{c}}%bid
%\newcommand{\probwin}{\ensuremath{P}}%probability of winning given bids
%
%\newcommand{\btos}{\text{\emph{BeliefsToStrategy}}}
%\newcommand{\br}{\text{\emph{BestResponse}}}
%\newcommand{\ul}{\text{\emph{UtilityLines}}}
%\newcommand{\fp}{\text{\emph{FictitiousPlay}}}
%\newcommand{\TRUE}{\text{\emph{true}}}
%\newcommand{\es}{\text{\emph{equilibrium strategy}}}
%\newcommand{\converged}{\text{\emph{converged}}}
%\newcommand{\convergedstrategy}{\text{\emph{ConvergedStrategy}}}
%\newcommand{\cost}{\text{\emph{cost}}}
%
%\newcommand{\supp}{\operatorname{supp}} 
%
%
%\newcommand{\etal}{{\em et al.}}
%
%
%
%\begin{document}

\section*{Review Responses}

\subsection{AE comments}

Overall, this paper attacks an important problem and describes a novel approach. However, the reviewers are agreed that the paper has serious drawbacks that preclude publication at this stage. In particular, they had concerns about the generality of the G-FACT class of games (and the extent to which restrictive assumptions were made clear), the applicability and scalability of the proposed algorithm, the extent to which connections were made to the published literature, and the paper's presentation. I recommend that the paper be accepted subject to the major revisions outlined by the reviewers.

\comment{
Thank you for obtaining these high quality reviews. We believe that we have dealt with all the issues that have been raised, apart from the ones where we explicitly stated we have not. For this latter category, we have detailed the rationale behind our choice. 

The major issues raised by the reviewers were regarding the generality of G-FACTs and restrictiveness of the assumptions, the scalability of the technique, and the lack of connections to related work. 

In terms of addressing these major issues, we have modified our paper as follows. We more clearly explain the restrictiveness of the assumptions when we introduce them (e.g., Section~\ref{sec:model}, first paragraph), provide an illustration of a G-FACT game using a standard single-item first-price auction (Example 1), and extend the technique to work with asymmetric games (Appendix A.1). 

We now provide a detailed demonstation of the scalability of our algorithm. In particular, in Section 6.2.2 we present empirical results showing how the number of iterations needed to reach convergence and the time taken by each iteration depends on the number of bidders (Fig. 7) and bid levels (Fig. 8). For most complementarity structures, the number of iterations before convergence is linear or sublinear indicating that the technique is scalable. However, time taken by each iteration grows superlinearly with the number of bidders and bid levels. To remedy this, we show how to make the technique scalable in the number of bidder by approximating the tie-breaking rule. Specifically, we introduce a new approach for approximating the expected utility which scales independently of the number of bidders (detailed in~\ref{sec:approxtie}). For the number of bid levels, the grows appears to be polynomial as we expect, since the number of actions equals the number of bids levels raised to the number of auctions.

Finally, Section 2 has been significantly expanded and now includes detailed connections to action graph games, as well as the other related work pointed out to us by the reviewers.


We provide details of how we deal with each issue raised by the reviews below.
}





\subsection{Reviewer 1}

In terms of organization and readability, I do not find this paper to be very reader-friendly.  Some aspects of the model and assumptions are glossed over and not well-motivated.  While the relation to prior work was discussed in the introduction and Section 2, I had trouble assessing it in the results for various classes of auctions in Section 6.  Which of these games precisely can and cannot be solved by prior techniques?  In the conclusion the authors state that an iterated best-response algorithm was applied unsuccessfully to some of the games on question, but the relation to prior work wasn't very clear to me when going over the results in Section 6 myself.

\comment{In the significantly expanded Section 2, we now spend more time explicitly stating the assumptions of our model and contrasting our work with existing techniques. We now mention in the first paragraph of Section 6 that there are no prior techniques for solving the games from this section.}


Introduction: ``There are no other solvers applicable to games of incomplete information" this isn't true, and is a pretty extreme claim.  Couterfactual regret (Zinkevich et al), excessive gap technique (Gilpin et al), and sequence-form LP (Koller et al) are obvious examples.  In addition, fictitious play (Ganzfried et al) has been successfully applied to games with incomplete information before.  The authors need to be careful about their claims.

\comment{The missing references have been included and discussed in relation to our paper in Section 2. We removed the claim, and emphasized the fact that unlike other techniques, ours applies to games with ``continuous types".}


References: I found it a strange that they were not in alphabetical order.  I guess they are in the order that they appear, which makes some sense.  I personally prefer alphabetical order, but I guess it's not a big deal.  

\comment{Fixed. Thanks for noticing this.}

 
Section 3 (definition of GFACT model): I found this section too dense/compact.  It is critical to present the model and assumptions in a clear, well-motivated way.  I think a simple example should be presented immediately.

\comment{We now provide an example in Section 3 (see Example 1). We also provide more explanation/motivation for the assumptions in Section 3 as well as the introduction.}

Why is it "standard" to only consider symmetric games, games where all players have the same finite set of actions, and games where the utility of a player is independent of the types of the other players and of the identity of the player performing the action?  What is the intuition behind each of these assumptions?

\comment{We have rephrased this to say that the following: ``As is common in much of the game-theoretic literature (see e.g.~\cite{krishnabook,mwg}), we focus on {\it symmetric} games (where all players have the same type-dependent utility function, set of action, value distribution, etc.) with single-dimensional types.'' Also, we relax the symmetry assumption in Appendix A.1. and mention this in footnote 1. 
}


Without discussing symmetric games or symmetric equilibria yet in the model so far, you define the "expected utility of type theta playing action $a_i$ when all other players follow the strategy s."  I found it a little bizarre that you sort of arbitrarily restrict all players to play the same strategy s without any discussion (even though you mentioned earlier in the introduction that you would be considering symmetric equilibria).

\comment{We now introduce symmetric Bayesian equilibrium before defining the expected utility for the case when everyone follows the same strategy (see second paragraph in Section 3). We also mention at the end of the first paragraph that an extension to asymmetric games are now presented in \ref{sec:asym}.
}



Does your algorithm apply if any of these assumptions are relaxed?

\comment{Yes, and to demonstrate this we now provide new material that extends the algorithm to asymmetric settings (i.e. where different players have different action spaces, type spaces, distributions, utility functions, etc.). In particular, in \ref{sec:asym} we extend the formalism to deal with asymmetric settings and introduce the Asymmetric Fictitious Play algorithm. We chose to maintain the formalism of symmetric games in the main body of the paper since this follows the convention of much of the existing literature and, we believe, makes it easier to follow. Furthermore, our experiments are entirely related to the symmetric setting.

Relaxing the single-dimensional type assumption is also possible, but less straightforward. We do not provide an algorithm for this, but in Appendix A.2 give some indication of how this could be done. Other assumptions, in particular independent private value and finite actions, are inherent to the algorithm as we state in the first paragraph of Section~\ref{sec:model}.} 

Again in section 4 you say "we extend fictitious play, which finds mixed equilibria in some complete information games, to search for pure strategy equilibria in games of incomplete information," the implication being that FP has not been applied to games of incomplete information previously (which it has).  The extension is to GFACTs, not to incomplete information.

\comment{We fixed this and are now explicit in saying that we mean application of FP to incomplete information games with *continuous types*. As we now mention, an advantage of our technique over techniques that use discrete types is that, in contrast to our technique, computational complexity of these techniques increases with the number of types. }


I wonder how a regret-minimizing algorithm would fare instead of fictitious play in your algorithm/analysis.  For example, it is known that CFR (Zinkevich/Bowling et al), a regret-matching algorithm, outperforms FP in some games.  I don't see why regret matching couldn't be applied to this setting also.

\comment{We now address this issue in Section 2 (Related work). To the best of our knowledge, regret-based algorithms have never been applied to games (of incomplete information) with continuous types. Nonetheless, we have incorporated the reference provided by the reviewer in a more explicit way in our discussion. It is necessary to point out that FP and regret converge under similar circumstances, although, in general, regret converges to a set (rather than a point) of correlated equilibria (this is now clarified in Section 2). We therefore preferred FP which guaranteed (if converged) a clearer choice of a single equilibrium strategy solution.}

Section 5: typo "Appendix Appendix A"

\comment{fixed}

Section 5 could really benefit from a simple auction example right from the start.  It is not necessarily intuitive why the "linearity of utility functions in theta" is interesting, though the authors do note that it is a weak assumption and is common in many interesting games.

\comment{We added an extensive example at the beginning of Section 3, which demonstrates the linearity assumption, and reference this example at the beginning of Section 5. We further motivate the linearity in Section 5.}

After the proof of Theorem 3, they claim "The last Theorem has high significance for practical application of FP, since it shows that an eps-equilibrium can be obtained by FP in finite time."  The fact that an algorithm is guaranteed to converge in finite time does not have any implication per se for practical application (e.g., brute-force exponential-time algorithms may be guaranteed to converge, but they may not be efficient in practice).  In addition, it has been proven that FP can sometimes require an exponential number of steps to converge even when convergence is guaranteed (Brandt et al).  

\comment{The claim has been removed.}

\subsection{Reviewer 2}

My concerns about the paper relate to the scope of applicability of the method, and unanswered questions regarding its scalability to realistic auction environments or other practical problems.  Regarding scope, the paper's title and the author's name for the class of games addressed (G-FACT) is somewhat misleading.  In addition to finite actions and continuous types, the methods seem to inherently require that (i) types are symmetric and independently distributed across players, (ii) types are one-dimensional, and (iii) action utilities are linear in type.  Requirement (i) is fairly common albeit restrictive, (ii) is quite limiting though does cover many useful game classes, and (iii) is really a serious limitation, not at all realistic even for the auction domain used as the prime example.  The text suggests that some of these requirements may be relaxable to some degree, but this issue needs to be addressed much more directly, with explicit statements about which
assumptions are necessary for which characteristics of the algorithm and application.

\comment{To improve clarity and avoid confusion, we have now grouped all the assumptions regarding the G-FACTS model in the first paragraph of Section 3 (before we mention the term G-FACTs), and we note which of these assumptions can be relaxed (i.e., symmetry and single-dimensional valuations) and this is further discussed in Appendix A, where we provide an algorithm for asymmetric settings, and discuss multi-dimensional types. The linearity assumption (iii) does not apply to the FP algorithm, and as such does not appear in Sections 3 and 4. It only comes into play when we instantiate the BestResponse and BeliefsToStrategy algorithms, but other algorithms could be implemented and this is not an inherent limitation of the FP algorithm. We clarify this in the beginning of Section 5. Furthermore, we argue that linearity (assumption (iii)) is natural in single-parameter domains (see first paragraph of Section 5). The same argument applies to linearity in multi-parameter domains. The title and the name G-FACTs were chosen to convey the main features of the model (i.e., finite actions and continuous types) while further modelling choices are clearly stated in the paper in the beginning of Section~\ref{sec:model}. Given this and considering that it is not practical to enumerate in the title all of the assumptions and the degrees to which the model relies on them, we feel the name G-FACTs is a reasonable choice. We comment on the scalability below.
}



The paper presents numerical computational results, but nothing about computational resources, either in terms of asymptotic complexity or observed runtimes.  This is an important omission, as any judgment about the utility of this approach must rest on the potential for application to problems of at least moderate complexity.  The auction examples are all fairly small, and there is no characterization of scalability based on number of players, goods, or bid levels.  The maximum number of bid levels employed in the results derived here is 10, which is far too coarse for any practical auction environment.

\comment{We now include new computational results and analysis in section 6.2.2., measuring runtimes and analysing scalability. In doing so, we consider both the scalability of the players and the number of bid levels (to maintain consistency, throughout we keep the number of auctions fixed to 2). In this section we now also discuss the runtime of our algorithms. In addition, to further improve the scalability of our approach, we now introduce an approximation of the fair tie breaking rule when calculating the expected utility, which allows the number of players to scale without additional computational complexity, and we analyse the error introduced by this approximation. The details of the approximate tie breaking rule are provided in~\ref{sec:approxtie}.} 
         
It would also be helpful to have a more explicit discussion of how this extension of FP relates to other literature on FP.  Are there alternative approaches to apply FP in an incomplete info setting, and if so how does your approach relate to these?  

\comment{Incomplete information games with finite types can be viewed as complete information games with a separate player corresponding to each type. Thus, FP can be applied directly to such games. However, the computational complexity of doing so increases exponentially with the number of types. This is now discussed in Section 2. We are not aware of any approach to apply FP to games with continuous type spaces, which are cardinally larger than the commonly considered discrete finite type spaces.}


Detailed Comments

\comment{We would like to thank the reviewer for the detailed and helpful comments.}


I. Substance
   
p2, l46.  You actually cite some other solvers that apply to games of incomplete information, so this sentence is obviously too sweeping.  

\comment{Rephrased to say ``most other solvers are not applicable to games of incomplete information with continuous types"}


p2, l50.  Again too sweeping.  It is not standard in g-t literature to focus on symmetric games.  

\comment{This is now rephrased. Furthermore, we extend the algorithm to asymmetric settings in~\ref{sec:asym}.}

p3, l35.  What is the basis for claim that pure equilibria are more "practical and desirable" than mixed?

\comment{We provided an argument in Footnote~\ref{fn:pure}.}


p4, l10.  Dubious assertion that linearity is a weak assumption, and "holds for most commonly studied games".  First, the quantification here is over a highly ambiguous domain.  Second, the follow-up claim that it holds for auctions is simply untrue except for the special case of single-good auctions.  Off the top of my head, I cannot think of works on multi-good auctions (e.g., multi-unit or combinatorial) that inherently assume and argue for the generality of a linearity assumption.

\comment{We fixed the assertion to talk about linearity in single-parameter domains. In domains like combinatorial auctions where a player has a separate type for each bundle, utility is linear in the bundle's type in the outcomes where the player wins the bundle (see Footnote~\ref{fn:linear} for the single-parameter explanation).}



p4, l26.  Not clear what is meant by "nearly complete", and as noted there are many restrictive assumptions.    

\comment{Removed this sentence.}


p5, l51.  Misleadingly suggests that the cited works are restrictive whereas the present work's methods are not.  You need to be much more precise about what the cited works cover, and how their restrictions compare to yours.  I doubt that any of these subsumes the others.

\comment{The misleading sentence is gone, and we provided much more detail in the related work section.}

p5, l52.  What are "structured games"?  

\comment{Replaced this terminology with specific examples.}

p7, l50.  It is confusing to use both X and theta for types.  Why not stick with theta?    

\comment{ We want to avoid using subscripts on theta (i.e., we prefer referring to an agent's type as theta rather than $\theta_i$).}


p8, l20.  Displayed equation uses i as two different variables.  

\comment{Fixed.}


p11, l24.  s* notation not defined

\comment{Rephrased the theorem to make it clear that $s^*$ denotes a strategy.}



p11, l41.  This correspondence defines the *pure* best responses.  

\comment{Fixed: a parenthesised notice added, as recommended}


p11, l50.  Not defined how you integrate over a correspondence.  

\comment{The integration is not over the correspondence, but rather of the correspondence. We have added a definition to clarify this point, and define the integral of the correspondence as the set of integral outcomes of all selector functions of that correspondence.}


p13, l47.  The best response function needs h as an argument.  Should this be s* as above?

\comment{We have now made the notation consistent, so that $s^*$, as any strategy, is always a function of just one argument - type.
}


p13, l50.  Awkward "them" in reference to utility lines.  Should explicitly note that there is a utility line for each combination of $a_i$ and h.

\comment{Fixed.
}


p15, l11.  $c \cup 1$ makes no sense, as neither operand is a set.    

\comment{Corrected to read $\type \in \{\i_i\}_{i=1}^{m'-1} \cup \{1\}$}


p15, l20.  Really would make more sense to define algorithm as taking h as input.  The utility lines are derived from this.  Ditto for algorithm of Fig4.

\comment{Added an algorithm (called UtilityLines, see Figure~\ref{fig:ul}) that explicitly lists arguments needed to compute utility lines. The algorithm is called from the BestResponse algorithm. Note that BeliefsToStrategy does not need to rely on the utility lines, so they are not passed there at all.}


p15, l25.  Need to make clear that the indices reflect sorting.

\comment{Fixed.}

p15, l30.  You already introduced $m = |A|$, so should use that.

\comment{Fixed.}



p15, l33.  "elements in c above x" is vague.  Actually this whole step needs to be rewritten to make a precise statement.

\comment{Rephrased the sentence and added a formal description.}


p15, l48.  "appropriate purification procedures are guaranteed to exist" is a vague assertion, particularly as appropriateness is completely undefined.

\comment{``appropriate'' was replaced by ``necessary'', as it refers to a necessary algorithmic step to obtain the needed pure strategy.}


p16, l19.  "sort actions in A' according to their slope"  Actually you mean the slope of their corresponding utility lines.                                                                                        

\comment{Fixed.}

p16, l33.  "equilibrium distribution of actions h*" not defined.  I can figure out what you must mean, but you really need to be explicit.

\comment{We meant converged distribution of actions. Fixed now.}



p16, l34.  Do you mean *the* equilibrium distribution, or *an* equilibrium distribution?

\comment{ *An* equilibrium distribution. Thanks!}


p16, l47.  "any best response is fully captured by its..."  I think you mean to say that that the best response can be expressed using the interval rep'n.

\comment{We rephrased the sentence as you suggested.}

p16, l51.  "the length of interval i"  You have not introduced any indexing of intervals.

\comment{Fixed.}


p16, Thm 2.  The proof seems right, but it could be explained much better.

\comment{More explanation has been added to the proof.}

p17, l22.  Why use absolute value for a difference when you know which term is larger?  (here and elsewhere)  

\comment{Using absolute value for a difference removes the need to trace the order of difference arguments throughout the proof. As a result, we can switch the order of arguments where it is more convenient for visual exposition, especially where we use the triangle inequality.}


p18, l47.  b should be a

\comment{Fixed.}

p19, l15.  Not really valid to motivate the analysis with examples of applications of simultaneous *ascending* auctions.  Your method applies only to one-shot auction mechanisms.

\comment{Removed references to simultaneous auctions.}


p19, l30.  Another non sequitur.  The weak equivalence of second-price to English holds only for the single auction case, which is expressly not what you are concerned with here.

\comment{Removed as well.}



p19, l46.  Here and throughout, you are identifying "substitutable" with "subadditive".  These are not technically the same thing.  Your usage throughout corresponds to sub- or super-additivity.  

\comment{Added a footnote to clarify our usage.}

p20, l20.  "This is realistic since in practice currencies have a smallest denomination."  This argument is really weak unless you can practically scale your algorithm to handle instances with bid levels at this granularity.  Presumably you want to handle auctions with values greater than 10 cents.

\comment{The algorithm scales to more than 10 bids as we now report in Section 6.}


p20, l32.  The tone of discussion here fails to acknowledge how limiting your assumptions here.  Basically, the symmetry and linearity assumptions means that the type is just a scaling factor.  Everyone has exactly the same relative preference among all good bundles.  This is not at all reasonable for any application that I know of, and indeed all other literature on multi-good auctions is motivated by allowing more flexibility than this.

\comment{We are now explicit about the restrictiveness of our assumptions (see paragraph 2 of Section~\ref{sec:sva}).}



p20, l46.  "extreme degree of substitutability".  This is highly nonstandard usage.  Most literature assumes free disposal, and so the extreme of substitutability is what you call "perfect substitutes".  Indeed, it seems quite strange to allow something more extreme than "perfect".  

\comment{This is done only for completeness (our analytical results hold for extreme substitutes). We now mention this explicitly (see paragraph 3 of Section~\ref{sec:sva}). }


p23, l40.  Not clear why relative "error" is more meaningful than absolute.  Utility is an interval scale, not ratio.      

\comment{This is now explained in Footnote~\ref{fn:error}.}

p24, l54.  Do you mean distance between strategies, or the induced action distributions?  It does not seem possible that it could be strategies, since as you show there are indifference cases that allow continua of strategies to produce the same action distributions.  The choice among these is arbitrary.  

\comment{We indeed meant the latter (action distribution). This has now been fixed.}

p37, l47.  Theorem statements need to be self-contained.  So you have to explicitly mention the assumption of linear utility and anything else that would qualify the result.

\comment{Fixed.}





II. Pure Exposition

p1. "In this paper" goes without saying in the abstract and introduction of the paper.      

\comment{We have removed these expressions, where obsolete}

p3, l18, l24.  Two instances of assertions that something is "natural", which is an essentially meaningless claim.  (There are other instances throughout the paper.)

\comment{additional explanation was added and sentences rephrased to remove the ambiguity.}
                     
p3, l19.  What is "it" that naturally (see comment above) guarantees existence?    

\comment{The paragraph is expanded to include an explicit statement: ``it'' $-->$ ``..the combination of finite actions and continuous type distribution..''}

p4, l50.  "fundamental previously unsolved" is a strange phrase  

\comment{rephrased into "prominent, yet previously unsolved,"}

p5, l31.  If you cite a textbook [10] for a particular technical result, you should give a more precise pointer (e.g., to section or theorem or page number).    

\comment{this reference has been replaced by two specific journal paper references}

p8, l17.  "When all other agents..."  

\comment{The recommended correction has been introduced.}

p8, l32.  Use punctuation after displayed math if used as part of sentences.  (here and elsewhere)

\comment{We have tried to adhere to this recommendation.}

p9, l14.  "all auctions rules" (ungrammatical)  

\comment{Fixed}

p9, l34.  Not clear what "remarks" you are referring to.

\comment{Remarks on the applicability of GAMBIT in its documentations. We have corrected the text accordingly.}

p9, l47.  Introduces notation delta for best response but this is not used elsewhere as far as I noticed.

\comment{Fixed, the notation is aligned with the rest of the paper.}

p10, l28.  In the algorithm description you should mathematically define (or refer to a definition elsewhere of) the "best-response strategy".

\comment{Corrected, a reference to G-FACTs best-response definition has been introduced.}

p12, first para.   Very hard to follow.  

\comment{We have rephrased this paragraph. In general we have expanded the proofs of this paper to include more intuitions and verbal explanations.}                

p13, l31.  "complete a FP algorithm" is a strange phrase          

\comment{Corrected, "instantiated" was meant here}

p14, Fig2.  Graph uses v on axis rather than theta.

\comment{Figure was corrected, $\theta$ has been placed as the label}

p15, l12.  No parentheses around "step 4".      

\comment{Corrected}

p15, l50.  What does "promote a practical algorithm application" mean?

\comment{Rephrased. We meant that existence is insufficient within itself for a practical algorithm application.}

p15, l54.  "Algorithm Algorithm"  There are many instances of this xref error.

\comment{Corrected.}

p15, l22.  Would be clearer to say $c = (c_1,...,c-{m'-1})$, rather than $c\subseteq R^{m'-1}$    

\comment{Both notations have been merged to improve clarity.}

p16, l38.  "are proven in the following two theorems"  Theorems do not prove anything.  Theorems are proved.          

\comment{Rephrased: ``..subject of the following two theorems..''.}

p18, l45.  Make clear that you are identifying "numerically negligible probability" with the constant threshold delta.      

\comment{The sentence has been extended accordingly.}

p20, l11.  "a heterogeneous item" makes no sense

\comment{Fixed, sentence rephrased.}

p22, l14.  "uniform $\sim$ [0,1]" should be "$\sim$ U[0,1]"

\comment{Corrected, now reads "Uniform([0,1])"}

p22, l45.  "in the more complicated setting"  

\comment{Fixed}

p24, l14.  "opposite" should be "converse"  

\comment{Corrected.}

p27, l44.  Could use a more meaningful symbol than "x".  Similarly, avoid introducing w,x,y,z for thresholds a few pages later.

\comment{We now use $\hat{\gamma}_1$, $\hat{\gamma}_2$, \ldots}


p34, l16.  "derive equilibria and prove its uniqueness"  Number disagreement, here and in next sentence.

\comment{Fixed. Uniformity restored.}

p34, l51.  You mean the slope of the *utility envelope* of a best-response *strategy*.

\comment{The formulation has been corrected as suggested.}

p35, l13.  Really not necessary to call out Obs 2 as an explicitly displayed observation.  

\comment{We prefer to keep Observation 2 as we reference it in Section 7.1.}

p40, l27.  "These derivation"

\comment{Fixed}

p43, References.  It would be much more convenient if you alphabetized these by author.  Also, please check capitalization and other formatting issues throughout.

\comment{References sorted. Capitalisation resolved where noticed.}

p46, ref [39].  Author improperly abbreviated.

\comment{Corrected.}


\subsection{Reviewer 3}

Does it place new results in appropriate context with earlier work?  Not entirely.  It's not always clear what was in (or implied by) previous work (e.g., Ganzfried and Sandholm).  

\comment{We have expanded our discussion of differences with previous work (see Section~\ref{sec:related}). In particular, regarding the Ganzfried-Sandholm reference, we now point out in Section~\ref{sec:related} that their algorithm was designed in response to a poker-game competition, an inherently discrete typed problem (albeit of large scale). This is in contrast to our algorithm that is designed to work with continuous type spaces, which are cardinally larger than can be handled by Ganzfried-Sandholm algorithm. In general, this is the key difference between extant solvers and our approach: generic handling of continuous type spaces. We now point this out in the related work section.}

Is the paper sufficiently different from previous publications (including papers published in major conferences)?  Yes.

Does anything need to be added or deleted?  Yes (see below).

Is the result important enough to warrant publication?  Yes.

FORM

Does the abstract adequately reflect the contents?  No (and neither does the title).  A large portion of this paper is about auctions, and the abstract doesn't reflect that.

\comment{We did not want to mention auctions in the title as the technique applies to G-FACTs and auctions serve as but one example. We mention other potential applications (double auctions, Courtot/Bertrand duopoly, negotiation) on p.~\pageref{othergames}. We also now discuss that the technique has been successfully applied to double auctions in~\cite{ecs20991}.}



Does it contain adequate references to previous work?  No.  There's very little discussion of other algorithms for incomplete information games (e.g. [17], multi-agent influence diagrams (Koller and Milch), Bayesian action-graph games (Jiang and Leyton-Brown) )

\comment{We have expanded our ``Related Work'' section to include the discussion of the provided references. We thank the reviewer for pointing out the necessity to address the issue of game representation. However, it is important to notice that the provided references indeed refer to ways to represent a game, rather than to solve it. We have included a small discussion regarding the effects of changing the game's representation, as well as BAGGs and MAIDs capabilities (or rather difficulties) in capturing the games on which we focus in this paper. Namely, games of incomplete information with continuous types.}


Does it explain clearly what was done that is new? No.  For example, G-FACTs are presented as a straightforward representation, while using FP on incomplete-information games is presented, in several places, as completely novel.

\comment{We are now more clear about our novelty claims throughout the paper, and point out in Sections~\ref{sec:intro} and~\ref{sec:related} that the novelty of our approach lies in the application of FP to incomplete information games with *continuous types*.}


Do the figures help clarify the concepts in the paper? Mostly yes.  Figure 5 averages over too many cases. (It's not clear which games converge quickly and which do not.) Figures 6a, 10a and 11b are hard to read because of overlapping lines.

\comment{We added more detailed convergence results for specific complementarity structures (see Figures \ref{fig:time_n} and \ref{fig:time_d}). Furthermore, we changed the line style in the strategy figures so that overlapping lines can be better identified.}


Although both contributions are interesting and important, I believe this paper needs major revisions: the text frequently switches between the two topics, confusing the reader.  (e.g., when assumptions are made about the structure of the game, it's not clear whether these are a property of the auctions or a necessary condition on the input of the FP algorithm).  Both contributions also have individual shortcomings as well.

\comment{The paper flows from more general to more specific contributions. To assist the reader to follow this flow, we provide some grounded examples when discussing generic formulae or algorithms. For instance, while describing different elements of the general FP algorithm, in Section 3 we now provide an extensive example to help understand the setting. We have now clearly marked this as an example.  At the same time these examples prepare the reader for the latter, more auction specific material. We have augmented the text to make the distinction between examples and contributions clearer.}


There are a number of issues the algorithmic side.  The G-FACT representation is described without explicitly mentioning how $u$ is encoded.  Even for linear payoffs, this could be extremely large, e.g., a set of linear expressions that could grow exponentially in $n$.  

\comment{For the case of linear payoffs, each utility line is represented by two coefficients: the slope and the intercept. There is a line for each action, and an upper envelope can contain at most one segment from each line, so the representation of utility for a strategy consists of at most $m$ (where $m$ is the number of actions) line segments. There seems to be no exponential growth in the representation unless we misunderstand the comment (there is, however, exponential growth in the number of auctions, as the number of actions equals the number of bid levels per auction raised to the power of the number of auctions). We have clarified this in the text. First, we added a generic algorithm for computing the utility lines (Figure~\ref{fig:ul}). Furthermore, we discuss this algorithm in Section~\ref{sec:convergence} where we discuss the scalability of our approach.}


For FP to be practical (indeed for it to be a complete algorithm), there needs to be a subroutine that calculates expected utility lines.  Appendix B provides such a subroutine, but only for the special case of simultaneous Vickrey auctions with uniform tie-breaking.  

\comment{We provided a subroutine that explicitly lists the parameters required to compute the utility lines. There can be no general procedure as it is game specific (now stated on page~\pageref{ulalg}). We added a sentence describing how the procedure is instantiated for the simultaneous auction game.}

G-FACTs are described as being very general (e.g., capable of representing/solving double auctions, duopoly, negotiation, simultaneous first-price/all-pay auctions), but the algorithm is only evaluated on that special case.  To demonstrate the usefulness of FP, it would help to demonstrate its rate of convergence on many types of games.

\comment{The algorithm has been recently applied (see~\cite{ecs20991}) to simultaneous double auctions, providing addition convergence results. We now mention that at the end of the conclusion. We agree that applying the algorithm to other settings is an interesting direction for future work (mentioned on p. \pageref{futurework}): in fact, this is exactly the reason for presenting the results for the general G-FACTs model. The case of simultaneous auctions is a rather rich ``special case" which subsumes perfect substitutes, perfect complements and everything in between.}

The main problem with the auction analysis is that it mostly focuses on the special case of auctions with two bid levels.  Although the two bid level analysis is well done and deep, there's not enough connections to the more general case, e.g. showing how insights from the two bid level case apply when the number of levels increases.

\comment{We spent time on the analysis of the 2-bid case as this is the case we can solve analytically, and we want to provide parallel computational results. Also, the 2-bid case is the simplest possible case and provides a good starting point for analysing the game. The case of more than 2 bids for complementary items (Figure 13) follows the same step structure as the 2-bid case, as we now mention on p.~\pageref{compitems}. We wish we were able to establish connections for the case of substitutable items, but the equilibria we discovered (Figure 14) did not exhibit a discernable general structure precluding connections with the 2-bid case.}


Section 7 doesn't contribute much value.  The polynomial equalities method seems like a very inefficient algorithm, and the results from the second half just analytically confirm what was already shown computationally.

\comment{The analytical results (Figure 15) provide *exact* pure strategy equilibria, while computationally we find approximate equilibria. Furthermore, analytical results prove uniqueness of equilibrium, which our computational technique does not do. Arguably, computational efficiency is less of an issue when talking about algorithms that output analytical results: analytical results need to be generated only once. Finding equilibria analytically even in simple settings such as single-item first price auction with discrete bids~\cite{chwe_89} is a non-trivial problem. We were able to derive the first analytical results for a model that is significantly more complex than the single-item auction for which analytical results exist. We feel these contributions are significant, and the other reviewers did not raise concerns regarding the contribution of this section.}

What happens in all bidders bid zero on an item?  This issue becomes especially important when disposal is not free.

\comment{Indeed, bidding zero is not the same as not bidding. If all bidders bid zero, then the tie-breaking rule applies and each bidder wins with equal probability (and pays zero). At present, the paper does not let bidders to not bid at all. One can include an additional ``no bid'' action to allow for this.}

%\end{document}
